package com.leet.tree;

import java.util.*;

public class PreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if(root == null) return ans;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode top = s.pop();
            ans.add(top.val);
            // 这个顺序比较重要，相对于层序遍历来说，先右后左，出来的时候先左后右，符合先序遍历。
            if(top.right != null) s.push(top.right);
            if(top.left != null) s.push(top.left);
        }
        return ans;
    }
}
